class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()

        len1 = len(nums1)
        len2 = len(nums2)

        (nums1, nums2, len1, len2) = (nums1, nums2, len1, len2) if (
            len1 < len2) else (nums2, nums1, len2, len1)

        res = []
        j = 0
        for n in nums1:
            while j < len2 - 1 and nums2[j] < n:
                j += 1

            if nums2[j] == n:
                res.append(n)
                j += 1

            if j >= len2:
                return res

        return res

# 出现了多次边界相关的问题，需要思考下


s = Solution()
print(s.intersect([21,47,80,4,3,24,87,12,22,11,48,6,89,80,74,71,74,55,58,56,4,98,40,66,49,53,62,27,3,66,78,24,48,69,88,12,80,63,98,65,46,35,72,5,64,72,7,29,37,3,2,75,44,93,79,78,13,39,85,26,15,41,87,47,29,93,41,74,6,48,17,89,27,61,2,68,99,57,45,73,25,33,38,32,58],
[1,39,6,81,85,10,38,22,0,89,57,93,58,69,65,80,84,24,27,54,37,36,26,88,2,7,24,36,51,5,74,57,45,56,55,67,25,33,78,49,16,79,74,80,36,27,89,49,64,73,96,60,92,31,98,72,22,31,0,93,70,87,80,66,75,69,81,52,94,90,51,90,74,36,58,38,50,9,64,55,4,21,49,60,65,47,67,8,38,83]))
print(s.intersect([5,0,0,6,1,6,2,2,4], [4,7,9,7,6,7]))
print(s.intersect([1, 2, 2, 1], [2, 2]))
